

In this here second part of the "Timestamped" series, we introduce the namesake Timestamped interface, and use a Deque from Java 1.6 to collect such things, but introducing a time-based capacity. 

<!--break-->

Ultimately we gonna hook up a remote Log4j appender, to display stats on demand via HTTP, and notify ourselves via Gtalk when the wheels are coming off. <i>An appender that is itself a webserver and XMPP communicator? What fun!</i> But lemme not get ahead of myself.

<h3>Prequels</h3>

Incidently we kicked off this no-hit wonder series with <a href="http://weblogs.java.net/blog/evanx/archive/2012/06/07/counter-map">Counter Map</a>, which does not feature further yet, so ignore that for now.

<p>   
<a style='text-decoration: none;' href="https://code.google.com/p/vellum/wiki/home">
<div style="border-bottom: solid 1px; background-color: #ccff00;">
<img src="http://upload.wikimedia.org/wikipedia/commons/1/12/Gnome-appointment-new.svg" border="0" align="left" hspace="0"/><span style="font-style: normal; font-weight: bold; font-size: 12pt;">&nbsp;Timestamped Deque:</span><span style="font-style: italic; font-weight: normal; font-size: 11pt;">&nbsp;A part of "Timestamped: a trilogy in a few parts."</span>
</div>
</a>

Without further ado, I give you the namesake interface of this series.
<pre>
public interface Timestamped {
    public long getTimestamp();    
}
</pre>
which returns the timestamp in "millis" ala <tt>System.currentTimeMillis()</tt>.

Also take an adapter for a Log4j logging event. 
<pre>
public class TimestampedLoggingEventAdapter implements Timestamped {
    LoggingEvent loggingEvent;

    public TimestampedLoggingEventAdapter(LoggingEvent loggingEvent) {
        this.loggingEvent = loggingEvent;
    }

    @Override
    public long getTimestamp() {
        return loggingEvent.getTimeStamp();
    }
}
</pre>
And a generic wrapped element.
<pre>
public class TimestampedElement<T> implements Timestamped {
    T element;
    long timestamp;

    public TimestampedElement(T element, long timestamp) {
        this.element = element;
        this.timestamp = timestamp;
    }

    public T getElement() {
        return element;
    }
    
    @Override
    public long getTimestamp() {
        return timestamp;
    }
}
</pre>
We might want equality by the timestamp for this element.
<pre>
    @Override
    public int hashCode() {
        return (int) (timestampMillis & Integer.MAX_VALUE);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Timestamped) {
            return timestamp == ((Timestamped) obj).getTimestamp();
        }
        return false;
    }
</pre>
By my calculation, that <tt>hashCode()</tt> is good for a cycle of 24 days of millis without any collisions.

We assume duplicates are possible i.e. where two or more events have the same millisecond timestamp, and so we might loose records if we add such elements to a <a href="http://docs.oracle.com/javase/6/docs/api/java/util/Set.html"><tt>Set</tt></a>, because its javadoc describes it thus,
<blockquote>
    <tt>Set</tt> - A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e)
</blockquote>

Also, a comparator will undoubtedly be required at some stage. 
<pre>
public class TimestampedComparator implements Comparator<Timestamped> {

    @Override
    public int compare(Timestamped o1, Timestamped o2) {
        if (o1.getTimestamp() < o2.getTimestamp()) return -1;
        if (o1.getTimestamp() > o2.getTimestamp()) return 1;
        else return 0;
    }    
}
</pre>

Again, if we use this <tt>Comparator</tt> to construct a <a href="http://docs.oracle.com/javase/6/docs/api/java/util/SortedSet.html"><tt>SortedSet</tt></a> of <tt>Timetamped</tt> elements, we might loose some.
<blockquote>
    <tt>SortedSet</tt> - The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time.
</blockquote>
        
So our inclination would be collect <tt>Timestamped</tt> elements in a <a href="http://docs.oracle.com/javase/6/docs/api/java/util/List.html"><tt>List</tt></a>, or a <a href="http://docs.oracle.com/javase/6/docs/api/java/util/Queue.html"><tt>Queue</tt></a> perhaps.
<blockquote>
    <tt>Queue</tt> - A collection designed for holding elements prior to processing.
</blockquote>
That sounds rather appropriate for our digestive purposes. 

<h2>Deque Collector</h2>

Now let's introduce the crux of this article, a collector of timestamped thingies, with a time-based capacity - a <a href="http://en.wikipedia.org/wiki/Circular_buffer">circular buffer</a>, some might call it.

So we use the <a href="http://docs.oracle.com/javase/6/docs/api/java/util/Deque.html">java.util.Deque</a> found in Java 1.6, courtesy of those most excellent gentlemen, Doug Lea and Josh Bloch. Its javadoc describes it thus...
<blockquote>
    <tt>Deque</tt> - A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck."
</blockquote>
We use the efficient <a href="http://docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html"><tt>ArrayDeque</tt></a> implementation.
<blockquote>
<tt>ArrayDeque</tt> - This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
</blockquote>
Fantastic. Let's get us some of that.
<pre>
public class TimestampedDequer<T extends Timestamped>  {
    long capacityMillis;
    long lastTimestamp;
    ArrayDeque<T> deque = new ArrayDeque();
    
    public TimestampedDequer(long capacityMillis) {
        this.capacityMillis = capacityMillis;
    }
    
    public synchronized void addLast(T element) {
        if (element.getTimestamp() == 0 || element.getTimestamp() < lastTimestamp) {
            deque.clear(); // throw our toys out the cot exception
        } else {
            lastTimestamp = element.getTimestamp();
            prune(lastTimestamp);
            deque.addLast(element);
        }
    }

    private void prune(long latestTimestamp) {
        while (deque.size() > 0 && 
                deque.getFirst().getTimestamp() <= latestTimestamp - capacityMillis) {
            deque.removeFirst();
        }
    }
}
</pre>
where we compose an <tt>ArrayDeque</tt> and <tt>synchronize</tt> it "externally" for our purposes, considering that it will be digesting log records continually, whilst being under interrogation by HTTP requests and what-not. 

<img src="http://jroller.com/evanx/resource/top-deck-mint-crop3.jpg" align="left" hspace="16"/>
Crucially, when we add an element at the tail, we <tt>prune()</tt> older elements from the head, so that our list is not growing out of control. We wanna keep it minty.

Observe that the <tt>prune()</tt> implementation assumes that elements are added in chronological order. If we are digesting logs from multiple servers or what-have-you, the above so-called "dequer" aint gonna work. <i>It's gonna come up empty, baby. So don't shuffle this deque, baby. (As Elvis might have said.)</i>

However we expect our host's time to be adjusted by <tt>NTP</tt> occassionally - hence the <tt>deque.clear()</tt>.

In order to analyse the contents for the desired interval, we take a <tt>snapshot()</tt>.
<pre>
    public synchronized Deque<T> snapshot(long lastTimestamp) {
        prune(lastTimestamp);
        return deque.clone();
    }
</pre>
which returns a defensive copy, and so is a relatively costly operation. Perhaps you could recommend an alternative strategy? Perhaps we could implement a special concurrent deque implementation in a future episode, as a fun exercise? Taking inspiration from that <a href="http://mechanitis.blogspot.com/2011/06/dissecting-disruptor-whats-so-special.html">Disruptor</a> thingymajig, perchance, as well as <tt>ArrayDeque</tt> itself?

Another use case is to get the tail i.e. the latest so-many elements e.g. for us to display in a servlet. 
<pre>
    public synchronized Deque<T> tail(int size) {
        Deque tail = new ArrayDeque();
        Iterator<T> it = deque.descendingIterator();
        for (int i = 0; i < size && it.hasNext(); i++) {
            tail.addFirst(it.next());
        }
        return tail;
    }    
</pre>

Let's test this thing. 
<pre>
public class TimestampedDequerTest  {
    final TimestampedDequer<TimestampedElement> dequer = new TimestampedDequer(capacityMillis);
    boolean verbose = false;
    
    private void addLast() {
        long timestamp = System.currentTimeMillis();
        String value = "record at " + timestamp;
        dequer.addLast(new TimestampedElement(value, timestamp));
        if (verbose) {
            System.out.println(value);
        }
    }

    @Test
    public void test() throws Exception {
        Assert.assertEquals(0, dequer.tail(2).size());
        check();
        check();
    }
</pre>
where we check twice, just to make sure of the <tt>prune()</tt>'ing. 
<pre>
    private void check() throws Exception {
        Thread.sleep(capacityMillis);
        Assert.assertEquals(0, dequer.snapshot(System.currentTimeMillis()).size());
        Assert.assertEquals(0, dequer.tail(2).size());
        addLast();
        Assert.assertEquals(1, dequer.tail(2).size());
        Assert.assertEquals(1, dequer.snapshot(System.currentTimeMillis()).size());
        Thread.sleep(capacityMillis/2);
        Assert.assertEquals(1, dequer.snapshot(System.currentTimeMillis()).size());
        Assert.assertEquals(1, dequer.tail(2).size());
        addLast();
        Assert.assertEquals(2, dequer.tail(5).size());
        Assert.assertEquals(2, dequer.snapshot(System.currentTimeMillis()).size());
        Thread.sleep(capacityMillis*2/3);
        Assert.assertEquals(2, dequer.tail(5).size());
        Assert.assertEquals(1, dequer.snapshot(System.currentTimeMillis()).size());
        Assert.assertEquals(1, dequer.tail(5).size());
    }
</pre>
where since we have slept for longer than the <tt>capacityMillis</tt>, and so we expect the first element to be <tt>prune()</tt>'ed off by the time of the final <tt>snapshot</tt>.

Given that the purpose of this Timestamped series is reducing information overload, we'll tail off here for now, and leave the threaded test for the next week.

Thereafter, we'll see about using it for real, to periodically analyse the latest deque of logs e.g. for the last minute, to detect when our app's wheels are wobbling or even coming off altogether.

<h3>Credits</h3>

Thanks to my colleague Zach Visagie at BizSwitch.net, for his kind reviews and indispensible input!

<h3>Resources</h3>

https://code.google.com/p/vellum/ - where i will collate these articles and their code.

